package _11_整理题目._4_动态规划._跳台阶_扔鸡蛋;

import org.junit.Test;

/**
 * https://leetcode.cn/problems/climbing-stairs/
 * 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
 * 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
 *
 * 1、递归
 * 2、记忆化搜索递归，从顶向下，搜索、记忆 mem[i]
 *
 * 3、动态规划，从底向上 计算所有的 dp[i]
 * 4、滚动数组
 */
public class _01_爬台阶 {

    public int climbStairs1(int n) {
        if(n < 3) return n;
        return climbStairs1(n-1) + climbStairs1(n-2);
    }

    public int climbStairs2(int n) {
        if(n < 3) return n;
        int[] mem = new int[n+1];
        return dfs(mem, n);
    }
    private int dfs(int[] mem, int n) {
        if(n < 3) return n;
        if (mem[n] == 0) {
            mem[n] = dfs(mem, n-1) + dfs(mem, n-2);
        }
        return mem[n];
    }

    public int climbStairs4(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;
        int a = 1, b = 2;
        int c = 0;
        for(int i=3; i<=n; i++) {
            c = a + b;
            a = b;
            b = c;
        }
        return c;
    }

    @Test
    public void main() {
        System.out.println(climbStairs1(30));
        System.out.println(climbStairs2(30));
        System.out.println(climbStairs4(30));
    }
}
